package algorithm.array;

import java.util.ArrayList;
import java.util.List;

/**
 *  杨辉三角
 *  In Pascal triangle , each number is the sum of the two numbers directly above it as shown;
 *
 *  example
 *  Input: numRows = 5
 *  Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
 */
public class PascalTriangle {

    public static void main(String[] args) {
        System.out.println(generate(4).toString());
    }

    public static List<Integer> generate(int numbers){

        List<List<Integer>> outlist = new ArrayList<>();

        for (int i = 0; i < numbers+1; i++) {
            List<Integer> list = new ArrayList<>();

            for (int j = 0; j <= i ; j++) {
                if (j == 0 || j == i ){
                    list.add(1);
                }else{
                    list.add(outlist.get(i-1).get(j-1) + outlist.get(i-1).get(j));
                }
            }
            outlist.add(list);
        }
        return outlist.get(numbers);
    }
}
